<!DOCTYPE html>
<html>
<!-- Created by GNU Texinfo 7.1.1, https://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<!-- Copyright © 1988-2023 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "Funding Free Software", the Front-Cover
Texts being (a) (see below), and with the Back-Cover Texts being (b)
(see below).  A copy of the license is included in the section entitled
"GNU Free Documentation License".

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU
     software.  Copies published by the Free Software Foundation raise
     funds for GNU development. -->
<title>The Language (GNU Compiler Collection (GCC) Internals)</title>

<meta name="description" content="The Language (GNU Compiler Collection (GCC) Internals)">
<meta name="keywords" content="The Language (GNU Compiler Collection (GCC) Internals)">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta name="viewport" content="width=device-width,initial-scale=1">

<link href="index.html" rel="start" title="Top">
<link href="Option-Index.html" rel="index" title="Option Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Match-and-Simplify.html" rel="up" title="Match and Simplify">
<link href="GIMPLE-API.html" rel="prev" title="GIMPLE API">
<style type="text/css">
<!--
a.copiable-link {visibility: hidden; text-decoration: none; line-height: 0em}
div.example {margin-left: 3.2em}
span:hover a.copiable-link {visibility: visible}
-->
</style>


</head>

<body lang="en">
<div class="section-level-extent" id="The-Language">
<div class="nav-panel">
<p>
Previous: <a href="GIMPLE-API.html" accesskey="p" rel="prev">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html" accesskey="u" rel="up">Match and Simplify</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<h3 class="section" id="The-Language-1"><span>26.2 The Language<a class="copiable-link" href="#The-Language-1"> &para;</a></span></h3>
<a class="index-entry-id" id="index-The-Language"></a>

<p>The language in which to write expression simplifications resembles
other domain-specific languages GCC uses.  Thus it is lispy.  Let&rsquo;s
start with an example from the match.pd file:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (bit_and @0 integer_all_onesp)
  @0)
</pre></div>

<p>This example contains all required parts of an expression simplification.
A simplification is wrapped inside a <code class="code">(simplify ...)</code> expression.
That contains at least two operands - an expression that is matched
with the GIMPLE or GENERIC IL and a replacement expression that is
returned if the match was successful.
</p>
<p>Expressions have an operator ID, <code class="code">bit_and</code> in this case.  Expressions can
be lower-case tree codes with <code class="code">_expr</code> stripped off or builtin
function code names in all-caps, like <code class="code">BUILT_IN_SQRT</code>.
</p>
<p><code class="code">@n</code> denotes a so-called capture.  It captures the operand and lets
you refer to it in other places of the match-and-simplify.  In the
above example it is referred to in the replacement expression.  Captures
are <code class="code">@</code> followed by a number or an identifier.
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (bit_xor @0 @0)
  { build_zero_cst (type); })
</pre></div>

<p>In this example <code class="code">@0</code> is mentioned twice which constrains the matched
expression to have two equal operands.  Usually matches are constrained
to equal types.  If operands may be constants and conversions are involved,
matching by value might be preferred in which case use <code class="code">@@0</code> to
denote a by-value match and the specific operand you want to refer to
in the result part.  This example also introduces
operands written in C code.  These can be used in the expression
replacements and are supposed to evaluate to a tree node which has to
be a valid GIMPLE operand (so you cannot generate expressions in C code).
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (trunc_mod integer_zerop@0 @1)
  (if (!integer_zerop (@1))
   @0))
</pre></div>

<p>Here <code class="code">@0</code> captures the first operand of the trunc_mod expression
which is also predicated with <code class="code">integer_zerop</code>.  Expression operands
may be either expressions, predicates or captures.  Captures
can be unconstrained or capture expressions or predicates.
</p>
<p>This example introduces an optional operand of simplify,
the if-expression.  This condition is evaluated after the
expression matched in the IL and is required to evaluate to true
to enable the replacement expression in the second operand
position.  The expression operand of the <code class="code">if</code> is a standard C
expression which may contain references to captures.  The <code class="code">if</code>
has an optional third operand which may contain the replacement
expression that is enabled when the condition evaluates to false.
</p>
<p>A <code class="code">if</code> expression can be used to specify a common condition
for multiple simplify patterns, avoiding the need
to repeat that multiple times:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(if (!TYPE_SATURATING (type)
     &amp;&amp; !FLOAT_TYPE_P (type) &amp;&amp; !FIXED_POINT_TYPE_P (type))
  (simplify
    (minus (plus @0 @1) @0)
    @1)
  (simplify
    (minus (minus @0 @1) @0)
    (negate @1)))
</pre></div>

<p>Note that <code class="code">if</code>s in outer position do not have the optional
else clause but instead have multiple then clauses.
</p>
<p>Ifs can be nested.
</p>
<p>There exists a <code class="code">switch</code> expression which can be used to
chain conditions avoiding nesting <code class="code">if</code>s too much:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
 (simple_comparison @0 REAL_CST@1)
 (switch
  /* a CMP (-0) -&gt; a CMP 0  */
  (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1)))
   (cmp @0 { build_real (TREE_TYPE (@1), dconst0); }))
  /* x != NaN is always true, other ops are always false.  */
  (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1))
       &amp;&amp; ! HONOR_SNANS (@1))
   { constant_boolean_node (cmp == NE_EXPR, type); })))
</pre></div>

<p>Is equal to
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
 (simple_comparison @0 REAL_CST@1)
 (switch
  /* a CMP (-0) -&gt; a CMP 0  */
  (if (REAL_VALUE_MINUS_ZERO (TREE_REAL_CST (@1)))
   (cmp @0 { build_real (TREE_TYPE (@1), dconst0); })
   /* x != NaN is always true, other ops are always false.  */
   (if (REAL_VALUE_ISNAN (TREE_REAL_CST (@1))
        &amp;&amp; ! HONOR_SNANS (@1))
    { constant_boolean_node (cmp == NE_EXPR, type); }))))
</pre></div>

<p>which has the second <code class="code">if</code> in the else operand of the first.
The <code class="code">switch</code> expression takes <code class="code">if</code> expressions as
operands (which may not have else clauses) and as a last operand
a replacement expression which should be enabled by default if
no other condition evaluated to true.
</p>
<p>Captures can also be used for capturing results of sub-expressions.
</p>
<div class="example smallexample">
<pre class="example-preformatted">#if GIMPLE
(simplify
  (pointer_plus (addr@2 @0) INTEGER_CST_P@1)
  (if (is_gimple_min_invariant (@2)))
  {
    poly_int64 off;
    tree base = get_addr_base_and_unit_offset (@0, &amp;off);
    off += tree_to_uhwi (@1);
    /* Now with that we should be able to simply write
       (addr (mem_ref (addr @base) (plus @off @1)))  */
    build1 (ADDR_EXPR, type,
            build2 (MEM_REF, TREE_TYPE (TREE_TYPE (@2)),
                    build_fold_addr_expr (base),
                    build_int_cst (ptr_type_node, off)));
  })
#endif
</pre></div>

<p>In the above example, <code class="code">@2</code> captures the result of the expression
<code class="code">(addr @0)</code>.  For the outermost expression only its type can be
captured, and the keyword <code class="code">type</code> is reserved for this purpose.  The
above example also gives a way to conditionalize patterns to only apply
to <code class="code">GIMPLE</code> or <code class="code">GENERIC</code> by means of using the pre-defined
preprocessor macros <code class="code">GIMPLE</code> and <code class="code">GENERIC</code> and using
preprocessor directives.
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (bit_and:c integral_op_p@0 (bit_ior:c (bit_not @0) @1))
  (bit_and @1 @0))
</pre></div>

<p>Here we introduce flags on match expressions.  The flag used
above, <code class="code">c</code>, denotes that the expression should
be also matched commutated.  Thus the above match expression
is really the following four match expressions:
</p>
<div class="example smallexample">
<pre class="example-preformatted">  (bit_and integral_op_p@0 (bit_ior (bit_not @0) @1))
  (bit_and (bit_ior (bit_not @0) @1) integral_op_p@0)
  (bit_and integral_op_p@0 (bit_ior @1 (bit_not @0)))
  (bit_and (bit_ior @1 (bit_not @0)) integral_op_p@0)
</pre></div>

<p>Usual canonicalizations you know from GENERIC expressions are
applied before matching, so for example constant operands always
come second in commutative expressions.
</p>
<p>The second supported flag is <code class="code">s</code> which tells the code
generator to fail the pattern if the expression marked with
<code class="code">s</code> does have more than one use and the simplification
results in an expression with more than one operator.
For example in
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (pointer_plus (pointer_plus:s @0 @1) @3)
  (pointer_plus @0 (plus @1 @3)))
</pre></div>

<p>this avoids the association if <code class="code">(pointer_plus @0 @1)</code> is
used outside of the matched expression and thus it would stay
live and not trivially removed by dead code elimination.
Now consider <code class="code">((x + 3) + -3)</code> with the temporary
holding <code class="code">(x + 3)</code> used elsewhere.  This simplifies down
to <code class="code">x</code> which is desirable and thus flagging with <code class="code">s</code>
does not prevent the transform.  Now consider <code class="code">((x + 3) + 1)</code>
which simplifies to <code class="code">(x + 4)</code>.  Despite being flagged with
<code class="code">s</code> the simplification will be performed.  The
simplification of <code class="code">((x + a) + 1)</code> to <code class="code">(x + (a + 1))</code> will
not performed in this case though.
</p>
<p>More features exist to avoid too much repetition.
</p>
<div class="example smallexample">
<pre class="example-preformatted">(for op (plus pointer_plus minus bit_ior bit_xor)
  (simplify
    (op @0 integer_zerop)
    @0))
</pre></div>

<p>A <code class="code">for</code> expression can be used to repeat a pattern for each
operator specified, substituting <code class="code">op</code>.  <code class="code">for</code> can be
nested and a <code class="code">for</code> can have multiple operators to iterate.
</p>
<div class="example smallexample">
<pre class="example-preformatted">(for opa (plus minus)
     opb (minus plus)
  (for opc (plus minus)
    (simplify...
</pre></div>

<p>In this example the pattern will be repeated four times with
<code class="code">opa, opb, opc</code> being <code class="code">plus, minus, plus</code>;
<code class="code">plus, minus, minus</code>; <code class="code">minus, plus, plus</code>;
<code class="code">minus, plus, minus</code>.
</p>
<p>To avoid repeating operator lists in <code class="code">for</code> you can name
them via
</p>
<div class="example smallexample">
<pre class="example-preformatted">(define_operator_list pmm plus minus mult)
</pre></div>

<p>and use them in <code class="code">for</code> operator lists where they get expanded.
</p>
<div class="example smallexample">
<pre class="example-preformatted">(for opa (pmm trunc_div)
 (simplify...
</pre></div>

<p>So this example iterates over <code class="code">plus</code>, <code class="code">minus</code>, <code class="code">mult</code>
and <code class="code">trunc_div</code>.
</p>
<p>Using operator lists can also remove the need to explicitly write
a <code class="code">for</code>.  All operator list uses that appear in a <code class="code">simplify</code>
or <code class="code">match</code> pattern in operator positions will implicitly
be added to a new <code class="code">for</code>.  For example
</p>
<div class="example smallexample">
<pre class="example-preformatted">(define_operator_list SQRT BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
(define_operator_list POW BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
(simplify
 (SQRT (POW @0 @1))
 (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); })))
</pre></div>

<p>is the same as
</p>
<div class="example smallexample">
<pre class="example-preformatted">(for SQRT (BUILT_IN_SQRTF BUILT_IN_SQRT BUILT_IN_SQRTL)
     POW (BUILT_IN_POWF BUILT_IN_POW BUILT_IN_POWL)
 (simplify
  (SQRT (POW @0 @1))
  (POW (abs @0) (mult @1 { built_real (TREE_TYPE (@1), dconsthalf); }))))
</pre></div>

<p><code class="code">for</code>s and operator lists can include the special identifier
<code class="code">null</code> that matches nothing and can never be generated.  This can
be used to pad an operator list so that it has a standard form,
even if there isn&rsquo;t a suitable operator for every form.
</p>
<p>Another building block are <code class="code">with</code> expressions in the
result expression which nest the generated code in a new C block
followed by its argument:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
 (convert (mult @0 @1))
 (with { tree utype = unsigned_type_for (type); }
  (convert (mult (convert:utype @0) (convert:utype @1)))))
</pre></div>

<p>This allows code nested in the <code class="code">with</code> to refer to the declared
variables.  In the above case we use the feature to specify the
type of a generated expression with the <code class="code">:type</code> syntax where
<code class="code">type</code> needs to be an identifier that refers to the desired type.
Usually the types of the generated result expressions are
determined from the context, but sometimes like in the above case
it is required that you specify them explicitly.
</p>
<p>Another modifier for generated expressions is <code class="code">!</code> which
tells the machinery to only consider the simplification in case
the marked expression simplified to a simple operand.  Consider
for example
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
  (plus (vec_cond:s @0 @1 @2) @3)
  (vec_cond @0 (plus! @1 @3) (plus! @2 @3)))
</pre></div>

<p>which moves the outer <code class="code">plus</code> operation to the inner arms
of the <code class="code">vec_cond</code> expression but only if the actual plus
operations both simplify.  Note that on <code class="code">GENERIC</code> a simple
operand means that the result satisfies <code class="code">!EXPR_P</code> which
can be limiting if the operation itself simplifies but the
remaining operand is an (unrelated) expression.
</p>
<p>As intermediate conversions are often optional there is a way to
avoid the need to repeat patterns both with and without such
conversions.  Namely you can mark a conversion as being optional
with a <code class="code">?</code>:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
 (eq (convert@0 @1) (convert? @2))
 (eq @1 (convert @2)))
</pre></div>

<p>which will match both <code class="code">(eq (convert @1) (convert @2))</code> and
<code class="code">(eq (convert @1) @2)</code>.  The optional converts are supposed
to be all either present or not, thus
<code class="code">(eq (convert? @1) (convert? @2))</code> will result in two
patterns only.  If you want to match all four combinations you
have access to two additional conditional converts as in
<code class="code">(eq (convert1? @1) (convert2? @2))</code>.
</p>
<p>The support for <code class="code">?</code> marking extends to all unary operations
including predicates you declare yourself with <code class="code">match</code>.
</p>
<p>Predicates available from the GCC middle-end need to be made
available explicitly via <code class="code">define_predicates</code>:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(define_predicates
 integer_onep integer_zerop integer_all_onesp)
</pre></div>

<p>You can also define predicates using the pattern matching language
and the <code class="code">match</code> form:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(match negate_expr_p
 INTEGER_CST
 (if (TYPE_OVERFLOW_WRAPS (type)
      || may_negate_without_overflow_p (t))))
(match negate_expr_p
 (negate @0))
</pre></div>

<p>This shows that for <code class="code">match</code> expressions there is <code class="code">t</code>
available which captures the outermost expression (something
not possible in the <code class="code">simplify</code> context).  As you can see
<code class="code">match</code> has an identifier as first operand which is how
you refer to the predicate in patterns.  Multiple <code class="code">match</code>
for the same identifier add additional cases where the predicate
matches.
</p>
<p>Predicates can also match an expression in which case you need
to provide a template specifying the identifier and where to
get its operands from:
</p>
<div class="example smallexample">
<pre class="example-preformatted">(match (logical_inverted_value @0)
 (eq @0 integer_zerop))
(match (logical_inverted_value @0)
 (bit_not truth_valued_p@0))
</pre></div>

<p>You can use the above predicate like
</p>
<div class="example smallexample">
<pre class="example-preformatted">(simplify
 (bit_and @0 (logical_inverted_value @0))
 { build_zero_cst (type); })
</pre></div>

<p>Which will match a bitwise and of an operand with its logical
inverted value.
</p>

</div>
<hr>
<div class="nav-panel">
<p>
Previous: <a href="GIMPLE-API.html">GIMPLE API</a>, Up: <a href="Match-and-Simplify.html">Match and Simplify</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
